/*
 *   This program is free software: you can redistribute it and/or modify
 *   it under the terms of the GNU General Public License as published by
 *   the Free Software Foundation, either version 3 of the License, or
 *   (at your option) any later version.
 *
 *   This program is distributed in the hope that it will be useful,
 *   but WITHOUT ANY WARRANTY; without even the implied warranty of
 *   MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE.  See the
 *   GNU General Public License for more details.
 *
 *   You should have received a copy of the GNU General Public License
 *   along with this program.  If not, see <http://www.gnu.org/licenses/>.
 */

/*
 *    HierarchicalBCEngine.java
 *    Copyright (C) 2003-2012 University of Waikato, Hamilton, New Zealand
 *
 */

package weka.gui.graphvisualizer;

import java.awt.GridBagConstraints;
import java.awt.GridBagLayout;
import java.awt.event.ActionEvent;
import java.awt.event.ActionListener;
import java.util.ArrayList;

import javax.swing.BorderFactory;
import javax.swing.ButtonGroup;
import javax.swing.JCheckBox;
import javax.swing.JPanel;
import javax.swing.JProgressBar;
import javax.swing.JRadioButton;

/**
 * This class lays out the vertices of a graph in a hierarchy of vertical
 * levels, with a number of nodes in each level. The number of levels is the
 * depth of the deepest child reachable from some parent at level 0. It
 * implements a layout technique as described by K. Sugiyama, S. Tagawa, and M.
 * Toda. in "Methods for visual understanding of hierarchical systems", IEEE
 * Transactions on Systems, Man and Cybernetics, SMC-11(2):109-125, Feb. 1981.
 * <p>
 * There have been a few modifications made, however. The crossings function is
 * changed as it was non-linear in time complexity. Furthermore, we don't have
 * any interconnection matrices for each level, instead we just have one big
 * interconnection matrix for the whole graph and a int[][] array which stores
 * the vertices present in each level.
 * 
 * @author Ashraf M. Kibriya (amk14@cs.waikato.ac.nz)
 * @version $Revision: 10502 $ - 24 Apr 2003 - Initial version (Ashraf M.
 *          Kibriya)
 * 
 */
public class HierarchicalBCEngine implements GraphConstants, LayoutEngine {

  /** FastVector containing nodes and edges */
  protected ArrayList<GraphNode> m_nodes;
  protected ArrayList<GraphEdge> m_edges;
  /**
   * FastVector containing listeners for layoutCompleteEvent generated by this
   * LayoutEngine
   */
  protected ArrayList<LayoutCompleteEventListener> layoutCompleteListeners;
  /** Interconnection matrix for the graph */
  protected int graphMatrix[][];
  /**
   * Array containing the indices of nodes in each level. The nodeLevels.length
   * is equal to the number of levels
   */
  protected int nodeLevels[][];
  /** The nodeWidth and nodeHeight */
  protected int m_nodeWidth, m_nodeHeight;

  /*
   * The following radio buttons control the way the layout is performed. If any
   * of the following is changed then we need to perform a complete relayout
   */
  protected JRadioButton m_jRbNaiveLayout;
  protected JRadioButton m_jRbPriorityLayout;
  protected JRadioButton m_jRbTopdown;
  protected JRadioButton m_jRbBottomup;

  /**
   * controls edge concentration by concentrating multilple singular dummy child
   * nodes into one plural dummy child node
   */
  protected JCheckBox m_jCbEdgeConcentration;

  /**
   * The panel containing extra options, specific to this LayoutEngine, for
   * greater control over layout of the graph
   */
  protected JPanel m_controlsPanel;

  /**
   * The progress bar to show the progress of the layout process
   */
  protected JProgressBar m_progress;

  /**
   * This tells the the LayoutGraph method if a completeReLayout should be
   * performed when it is called.
   */
  protected boolean m_completeReLayout = false;

  /**
   * This contains the original size of the nodes vector when it was passed in
   * through the constructor, before adding all the dummy vertices
   */
  private int origNodesSize;

  /**
   * Constructor - takes in FastVectors of nodes and edges, and the initial
   * width and height of a node
   */
  public HierarchicalBCEngine(ArrayList<GraphNode> nodes,
    ArrayList<GraphEdge> edges, int nodeWidth, int nodeHeight) {
    m_nodes = nodes;
    m_edges = edges;
    m_nodeWidth = nodeWidth;
    m_nodeHeight = nodeHeight;
    makeGUIPanel(false);
  }

  /**
   * Constructor - takes in FastVectors of nodes and edges, the initial width
   * and height of a node, and a boolean value to indicate if the edges should
   * be concentrated.
   * 
   * @param nodes - FastVector containing all the nodes
   * @param edges - FastVector containing all the edges
   * @param nodeWidth - A node's allowed width
   * @param nodeHeight - A node's allowed height
   * @param edgeConcentration - True: if want to concentrate edges, False:
   *          otherwise
   */
  public HierarchicalBCEngine(ArrayList<GraphNode> nodes,
    ArrayList<GraphEdge> edges, int nodeWidth, int nodeHeight,
    boolean edgeConcentration) {
    m_nodes = nodes;
    m_edges = edges;
    m_nodeWidth = nodeWidth;
    m_nodeHeight = nodeHeight;
    makeGUIPanel(edgeConcentration);
  }

  /**
   * SimpleConstructor If we want to instantiate the class first, and if
   * information for nodes and edges is not available. However, we would have to
   * manually provide all the information later on by calling setNodesEdges and
   * setNodeSize methods
   */
  public HierarchicalBCEngine() {
  }

  /**
   * This methods makes the gui extra controls panel "m_controlsPanel"
   */
  protected void makeGUIPanel(boolean edgeConc) {
    m_jRbNaiveLayout = new JRadioButton("Naive Layout");
    m_jRbPriorityLayout = new JRadioButton("Priority Layout");
    ButtonGroup bg = new ButtonGroup();
    bg.add(m_jRbNaiveLayout);
    bg.add(m_jRbPriorityLayout);
    m_jRbPriorityLayout.setSelected(true);

    ActionListener a = new ActionListener() {
      @Override
      public void actionPerformed(ActionEvent ae) {
        m_completeReLayout = true;
      }
    };

    m_jRbTopdown = new JRadioButton("Top Down");
    m_jRbBottomup = new JRadioButton("Bottom Up");
    m_jRbTopdown.addActionListener(a);
    m_jRbBottomup.addActionListener(a);
    bg = new ButtonGroup();
    bg.add(m_jRbTopdown);
    bg.add(m_jRbBottomup);
    m_jRbBottomup.setSelected(true);

    m_jCbEdgeConcentration = new JCheckBox("With Edge Concentration", edgeConc);
    m_jCbEdgeConcentration.setSelected(edgeConc);
    m_jCbEdgeConcentration.addActionListener(a);

    JPanel jp1 = new JPanel(new GridBagLayout());
    GridBagConstraints gbc = new GridBagConstraints();
    gbc.gridwidth = GridBagConstraints.REMAINDER;
    gbc.anchor = GridBagConstraints.NORTHWEST;
    gbc.weightx = 1;
    gbc.fill = GridBagConstraints.HORIZONTAL;
    jp1.add(m_jRbNaiveLayout, gbc);
    jp1.add(m_jRbPriorityLayout, gbc);
    jp1.setBorder(BorderFactory.createTitledBorder("Layout Type"));

    JPanel jp2 = new JPanel(new GridBagLayout());
    jp2.add(m_jRbTopdown, gbc);
    jp2.add(m_jRbBottomup, gbc);
    jp2.setBorder(BorderFactory.createTitledBorder("Layout Method"));

    m_progress = new JProgressBar(0, 11);
    m_progress.setBorderPainted(false);
    m_progress.setStringPainted(true);
    m_progress.setString("");

    m_progress.setValue(0);

    m_controlsPanel = new JPanel(new GridBagLayout());
    m_controlsPanel.add(jp1, gbc);
    m_controlsPanel.add(jp2, gbc);
    m_controlsPanel.add(m_jCbEdgeConcentration, gbc);
  }

  /** give access to set of graph nodes */
  @Override
  public ArrayList<GraphNode> getNodes() {
    return m_nodes;
  }

  /**
   * This method returns a handle to the extra controls panel, so that the
   * visualizing class can add it to some of it's own gui panel.
   */
  @Override
  public JPanel getControlPanel() {
    return m_controlsPanel;
  }

  /**
   * Returns a handle to the progressBar of this LayoutEngine.
   */
  @Override
  public JProgressBar getProgressBar() {
    return m_progress;
  }

  /**
   * Sets the nodes and edges for this LayoutEngine. Must be used if the class
   * created by simple HierarchicalBCEngine() constructor.
   * 
   * @param nodes - FastVector containing all the nodes
   * @param edges - FastVector containing all the edges
   */
  @Override
  public void setNodesEdges(ArrayList<GraphNode> nodes,
    ArrayList<GraphEdge> edges) {
    m_nodes = nodes;
    m_edges = edges;
  }

  /**
   * Sets the size of a node. This method must be used if the class created by
   * simple HierarchicalBCEngine() constructor.
   * 
   * @param nodeWidth - A node's allowed width
   * @param nodeHeight - A node's allowed height
   */
  @Override
  public void setNodeSize(int nodeWidth, int nodeHeight) {
    m_nodeWidth = nodeWidth;
    m_nodeHeight = nodeHeight;
  }

  /**
   * Method to add a LayoutCompleteEventListener
   * 
   * @param l - Listener to receive the LayoutCompleteEvent by this class.
   */
  @Override
  public void addLayoutCompleteEventListener(LayoutCompleteEventListener l) {
    if (layoutCompleteListeners == null) {
      layoutCompleteListeners = new ArrayList<LayoutCompleteEventListener>();
    }
    layoutCompleteListeners.add(l);
  }

  /**
   * Method to remove a LayoutCompleteEventListener.
   * 
   * @param e - The LayoutCompleteEventListener to remove.
   */
  @Override
  public void removeLayoutCompleteEventListener(LayoutCompleteEventListener e) {
    if (layoutCompleteListeners != null) {
      LayoutCompleteEventListener l;

      for (int i = 0; i < layoutCompleteListeners.size(); i++) {
        l = layoutCompleteListeners.get(i);
        if (l == e) {
          layoutCompleteListeners.remove(i);
          return;
        }
      }
      System.err.println("layoutCompleteListener to be remove not present");
    } else {
      System.err.println("layoutCompleteListener to be remove not present");
    }
  }

  /**
   * Fires a LayoutCompleteEvent.
   * 
   * @param e - The LayoutCompleteEvent to fire
   */
  @Override
  public void fireLayoutCompleteEvent(LayoutCompleteEvent e) {
    if (layoutCompleteListeners != null && layoutCompleteListeners.size() != 0) {
      LayoutCompleteEventListener l;

      for (int i = 0; i < layoutCompleteListeners.size(); i++) {
        l = layoutCompleteListeners.get(i);
        l.layoutCompleted(e);
      }
    }
  }

  /**
   * This method does a complete layout of the graph which includes removing
   * cycles, assigning levels to nodes, reducing edge crossings and laying out
   * the vertices horizontally for better visibility. The removing of cycles and
   * assignment of levels is only performed if hasn't been performed earlier or
   * if some layout option has been changed and it is necessary to do so. It is
   * necessary to do so, if the user selects/deselects edge concentration or
   * topdown/bottomup options.
   * <p>
   * The layout is performed in a separate thread and the progress bar of the
   * class is updated for each of the steps as the process continues.
   */
  @Override
  public void layoutGraph() {
    // cannot perform a layout if no description of nodes and/or edges is
    // provided
    if (m_nodes == null || m_edges == null) {
      return;
    }

    Thread th = new Thread() {
      @Override
      public void run() {
        m_progress.setBorderPainted(true);
        if (nodeLevels == null) {
          makeProperHierarchy();
        } else if (m_completeReLayout == true) {
          clearTemps_and_EdgesFromNodes();
          makeProperHierarchy();
          m_completeReLayout = false;
        }

        // minimizing crossings
        if (m_jRbTopdown.isSelected()) {
          int crossbefore = crossings(nodeLevels), crossafter = 0, i = 0;
          do {
            m_progress.setValue(i + 4);
            m_progress.setString("Minimizing Crossings: Pass" + (i + 1));
            if (i != 0) {
              crossbefore = crossafter;
            }
            nodeLevels = minimizeCrossings(false, nodeLevels);
            crossafter = crossings(nodeLevels);
            i++;
          } while (crossafter < crossbefore && i < 6);
        } else {
          int crossbefore = crossings(nodeLevels), crossafter = 0, i = 0;
          do {
            m_progress.setValue(i + 4);
            m_progress.setString("Minimizing Crossings: Pass" + (i + 1));
            if (i != 0) {
              crossbefore = crossafter;
            }
            nodeLevels = minimizeCrossings(true, nodeLevels);
            crossafter = crossings(nodeLevels);
            i++;
          } while (crossafter < crossbefore && i < 6);
        }
        // System.out.println("\nCrossings at the end "+
        // crossings(nodeLevels)+
        // "\n---------------------------------");

        m_progress.setValue(10);
        m_progress.setString("Laying out vertices");
        // Laying out graph
        if (m_jRbNaiveLayout.isSelected()) {
          naiveLayout();
        } else {
          priorityLayout1();
        }
        m_progress.setValue(11);
        m_progress.setString("Layout Complete");
        m_progress.repaint();

        fireLayoutCompleteEvent(new LayoutCompleteEvent(this));
        m_progress.setValue(0);
        m_progress.setString("");
        m_progress.setBorderPainted(false);
      }
    };
    th.start();
  }

  /**
   * This method removes the temporary nodes that were added to fill in the
   * gaps, and removes all edges from all nodes in their edges[][] array
   */
  protected void clearTemps_and_EdgesFromNodes() {
    /*
     * System.out.println("Before............."); for(int i=0; i<m_nodes.size();
     * i++) { GraphNode n = (GraphNode)m_nodes.get(i);
     * System.out.println("N: "+n.ID+","+i); }
     * System.out.println("origNodesSize: "+origNodesSize);
     */

    int curSize = m_nodes.size();
    for (int i = origNodesSize; i < curSize; i++) {
      m_nodes.remove(origNodesSize);
    }
    for (int j = 0; j < m_nodes.size(); j++) {
      m_nodes.get(j).edges = null;
    }

    nodeLevels = null;

    /*
     * System.out.println("After.............."); for(int i=0; i<m_nodes.size();
     * i++) { GraphNode n = (GraphNode)m_nodes.get(i);
     * System.out.println("N: "+n.ID+","+i); }
     */
  }

  /**
   * This method makes the "graphMatrix" interconnection matrix for the graph
   * given by m_nodes and m_edges vectors. The matix is used by other methods.
   */
  protected void processGraph() {
    origNodesSize = m_nodes.size();
    graphMatrix = new int[m_nodes.size()][m_nodes.size()];
    /*
     * System.out.println("The "+m_nodes.size()+" nodes are: "); for(int i=0;
     * i<m_nodes.size(); i++) System.out.println((String)m_nodes.get(i)+" ");
     * System.out.println("\nThe "+m_edges.size()+" edges are: "); for(int i=0;
     * i<m_edges.size(); i++) System.out.println((GraphEdge)m_edges.get(i));
     */
    for (int i = 0; i < m_edges.size(); i++) {
      graphMatrix[m_edges.get(i).src][m_edges.get(i).dest] = m_edges.get(i).type;
      /*
       * System.out.print("\t"); for(int i=0; i<graphMatrix.length; i++)
       * System.out.print(((GraphNode)m_nodes.get(i)).ID+" ");
       * System.out.println(""); for(int i=0; i<graphMatrix.length; i++) {
       * GraphNode n = (GraphNode)m_nodes.get(i); System.out.print(n.ID+"\t");
       * for(int j=0; j<graphMatrix[i].length; j++)
       * System.out.print(graphMatrix[i][j]+" "); System.out.println(""); }
       */
    }
  }

  /*
   * This method makes a proper hierarchy of the graph by first removing cycles,
   * then assigning levels to the nodes and then removing gaps by adding dummy
   * vertices.
   */
  protected void makeProperHierarchy() {
    processGraph();

    m_progress.setValue(1);
    m_progress.setString("Removing Cycles");
    // ****removing cycles
    removeCycles();

    m_progress.setValue(2);
    m_progress.setString("Assigning levels to nodes");
    // ****Assigning vertical level to each node
    int nodesLevel[] = new int[m_nodes.size()];
    int depth = 0;
    for (int i = 0; i < graphMatrix.length; i++) {
      assignLevels(nodesLevel, depth, i, 0);
    }

    for (int i = 0; i < nodesLevel.length; i++) {
      if (nodesLevel[i] == 0) {
        int min = 65536;
        for (int j = 0; j < graphMatrix[i].length; j++) {
          if (graphMatrix[i][j] == DIRECTED) {
            if (min > nodesLevel[j]) {
              min = nodesLevel[j];
            }
          }
        }
        // if the shallowest child of a parent has a depth greater than 1
        // and it is not a lone parent with no children
        if (min != 65536 && min > 1) {
          nodesLevel[i] = min - 1;
        }
      }
    }

    // System.out.println("");
    int maxLevel = 0;
    for (int element : nodesLevel) {
      if (element > maxLevel) {
        maxLevel = element;
        // System.out.println( ((GraphNode)m_nodes.get(i)).ID+" "+i+">"+
        // nodesLevel[i]);
      }
    }
    int levelCounts[] = new int[maxLevel + 1];

    for (int i = 0; i < nodesLevel.length; i++) {
      levelCounts[nodesLevel[i]]++;
    }
    // System.out.println("------------------------------------------");
    // ****Assigning nodes to each level
    int levelsCounter[] = new int[maxLevel + 1];
    nodeLevels = new int[maxLevel + 1][];
    for (int i = 0; i < nodesLevel.length; i++) {
      if (nodeLevels[nodesLevel[i]] == null) {
        nodeLevels[nodesLevel[i]] = new int[levelCounts[nodesLevel[i]]];
      }
      // nodeLevels[nodesLevel[i]].addElement(new Integer(i));
      // System.out.println(((GraphNode)m_nodes.get(i)).ID+" "+
      // nodesLevel[i]+">"+levelCounts[nodesLevel[i]]);
      nodeLevels[nodesLevel[i]][levelsCounter[nodesLevel[i]]++] = i;
    }

    m_progress.setValue(3);
    m_progress.setString("Removing gaps by adding dummy vertices");
    // *Making a proper Hierarchy by putting in dummy vertices to close all gaps
    if (m_jCbEdgeConcentration.isSelected()) {
      removeGapsWithEdgeConcentration(nodesLevel);
    } else {
      removeGaps(nodesLevel);
    }

    // After assigning levels and adding dummy vertices
    // System.out.print("\n\t");
    // for(int i=0; i<graphMatrix.length; i++)
    // System.out.print(((GraphNode)m_nodes.get(i)).ID+" ");
    // System.out.println("");
    // for(int i=0; i<graphMatrix.length; i++) {
    // System.out.print(((GraphNode)m_nodes.get(i)).ID+"\t");
    // for(int j=0; j<graphMatrix[i].length; j++)
    // System.out.print(graphMatrix[i][j]+" ");
    // System.out.println("");
    // }

    // ****Updating edges[][] array of nodes from
    // ****the interconnection matrix, which will be used
    // ****by the Visualizer class to draw edges
    for (int i = 0; i < graphMatrix.length; i++) {
      GraphNode n = m_nodes.get(i);
      int sum = 0;
      for (int j = 0; j < graphMatrix[i].length; j++) {
        if (graphMatrix[i][j] != 0) {
          sum++;
        }
      }

      n.edges = new int[sum][2];
      for (int j = 0, k = 0; j < graphMatrix[i].length; j++) {
        if (graphMatrix[i][j] != 0) {
          n.edges[k][0] = j;
          n.edges[k][1] = graphMatrix[i][j];
          k++;
        }
        // n.edges = graphMatrix[i];
      }
    }

    // Interconnection matrices at each level, 1 to n-1
    // printMatrices(nodeLevels);
  }

  /**
   * This method removes gaps from the graph. It doesn't perform any
   * concentration. It takes as an argument of int[] of length m_nodes.size()
   * containing the level of each node.
   */
  private void removeGaps(int nodesLevel[]) {
    int temp = m_nodes.size();
    int temp2 = graphMatrix[0].length, tempCnt = 1;

    for (int n = 0; n < temp; n++) {
      for (int i = 0; i < temp2; i++) {
        int len = graphMatrix.length;
        if (graphMatrix[n][i] > 0) {
          if (nodesLevel[i] > nodesLevel[n] + 1) {
            int tempMatrix[][] = new int[graphMatrix.length
              + (nodesLevel[i] - nodesLevel[n] - 1)][graphMatrix.length
              + (nodesLevel[i] - nodesLevel[n] - 1)];
            int level = nodesLevel[n] + 1;
            copyMatrix(graphMatrix, tempMatrix);

            String s1 = new String("S" + tempCnt++);
            m_nodes.add(new GraphNode(s1, s1, SINGULAR_DUMMY)); // true));
            int temp3[] = new int[nodeLevels[level].length + 1];
            // for(int j=0; j<nodeLevels[level].length; j++)
            // temp3[j] = nodeLevels[level][j];
            System.arraycopy(nodeLevels[level], 0, temp3, 0,
              nodeLevels[level].length);
            temp3[temp3.length - 1] = m_nodes.size() - 1;
            nodeLevels[level] = temp3;
            level++;
            // nodeLevels[level++].addElement(new Integer(m_nodes.size()-1));
            // System.out.println("len:"+len+","+nodesLevel[i]+","+
            // nodesLevel[n]);

            int k;
            for (k = len; k < len + nodesLevel[i] - nodesLevel[n] - 1 - 1; k++) {
              String s2 = new String("S" + tempCnt);
              m_nodes.add(new GraphNode(s2, s2, SINGULAR_DUMMY)); // true)
                                                                  // );
              temp3 = new int[nodeLevels[level].length + 1];
              // for(int j=0; j<nodeLevels[level].length; j++)
              // temp3[j] = nodeLevels[level][j];
              System.arraycopy(nodeLevels[level], 0, temp3, 0,
                nodeLevels[level].length);
              temp3[temp3.length - 1] = m_nodes.size() - 1;
              nodeLevels[level++] = temp3;
              // nodeLevels[level++].addElement(new Integer(m_nodes.size()-1));
              tempMatrix[k][k + 1] = tempMatrix[n][i];
              tempCnt++;
              if (k > len) {
                tempMatrix[k][k - 1] = -1 * tempMatrix[n][i];
              }
            }

            // temp[lastTempNodeCreated][targetNode]=temp[origNode][targetNode]
            tempMatrix[k][i] = tempMatrix[n][i];
            // System.out.println("k "+((GraphNode)m_nodes.get(k)).ID+
            // " i "+((GraphNode)m_nodes.get(i)).ID+
            // " n "+((GraphNode)m_nodes.get(n)).ID+
            // " len "+((GraphNode)m_nodes.get(len)).ID );
            // temp[origNode][firstTempNodecreated] = temp[origNode][targetNode]
            tempMatrix[n][len] = tempMatrix[n][i];
            // temp[firstTempNodeCreated][origNode] for reverse tracing
            tempMatrix[len][n] = -1 * tempMatrix[n][i];
            // temp[targetNode][lastTempNodecreated] for reverse tracing
            tempMatrix[i][k] = -1 * tempMatrix[n][i];

            // temp[lastTempNodeCreated][secondlastNode] for reverse tracing
            // but only do this if more than 1 temp nodes are created
            if (k > len) {
              tempMatrix[k][k - 1] = -1 * tempMatrix[n][i];
            }

            // temp[origNode][targetNode] = 0 unlinking as they have been
            // linked by a chain of temporary nodes now.
            tempMatrix[n][i] = 0;
            tempMatrix[i][n] = 0;

            graphMatrix = tempMatrix;
          } else {
            // ****Even if there is no gap just add a reference for the
            // ****parent to the child for reverse tracing, useful if the
            // ****there is a reversed edge from parent to child and therefore
            // ****visualizer would know to highlight this edge when
            // ****highlighting the child.
            graphMatrix[i][n] = -1 * graphMatrix[n][i];
          }
        }
      }
    }
    // Interconnection matrices at each level, 1 to n-1 after minimizing edges
    // printMatrices(nodeLevels);
  }

  /**
   * This method removes gaps from the graph. It tries to minimise the number of
   * edges by concentrating multiple dummy nodes from the same parent and on the
   * same vertical level into one. It takes as an argument of int[] of length
   * m_nodes.size() containing the level of each node.
   */
  private void removeGapsWithEdgeConcentration(int nodesLevel[]) {

    final int temp = m_nodes.size(), temp2 = graphMatrix[0].length;
    int tempCnt = 1;

    for (int n = 0; n < temp; n++) {
      for (int i = 0; i < temp2; i++) {
        if (graphMatrix[n][i] > 0) {
          if (nodesLevel[i] > nodesLevel[n] + 1) {
            // System.out.println("Processing node "+
            // ((GraphNode)m_nodes.get(n)).ID+
            // " for "+((GraphNode)m_nodes.get(i)).ID);
            int tempLevel = nodesLevel[n];
            boolean tempNodePresent = false;
            int k = temp;
            int tempnode = n;

            while (tempLevel < nodesLevel[i] - 1) {
              tempNodePresent = false;
              for (; k < graphMatrix.length; k++) {
                if (graphMatrix[tempnode][k] > 0) {
                  // System.out.println("tempnode will be true");
                  tempNodePresent = true;
                  break;
                }
              }
              if (tempNodePresent) {
                tempnode = k;
                k = k + 1;
                tempLevel++;
              } else {
                if (tempnode != n) {
                  tempnode = k - 1;
                }
                // System.out.println("breaking from loop");
                break;
              }
            }
            if (m_nodes.get(tempnode).nodeType == SINGULAR_DUMMY) {
              m_nodes.get(tempnode).nodeType = PLURAL_DUMMY;
            }
            if (tempNodePresent) {
              // Link the last known temp node to target
              graphMatrix[tempnode][i] = graphMatrix[n][i];
              // System.out.println("modifying "+
              // ((GraphNode)nodes.get(tempnode)).ID+
              // ", "+((GraphNode)nodes.get(n)).ID);
              // ///matrix[lastknowntempnode][source]=-original_val
              // ///graphMatrix[tempnode][n] = -graphMatrix[n][i];
              // System.out.println("modifying "+
              // ((GraphNode)nodes.get(i)).ID+
              // ", "+
              // ((GraphNode)nodes.get(tempnode)).ID);

              // and matrix[target][lastknowntempnode]=-original_val
              // for reverse tracing
              graphMatrix[i][tempnode] = -graphMatrix[n][i];
              // unlink source from the target
              graphMatrix[n][i] = 0;
              graphMatrix[i][n] = 0;
              continue;

            }

            int len = graphMatrix.length;
            int tempMatrix[][] = new int[graphMatrix.length
              + (nodesLevel[i] - nodesLevel[tempnode] - 1)][graphMatrix.length
              + (nodesLevel[i] - nodesLevel[tempnode] - 1)];
            int level = nodesLevel[tempnode] + 1;
            copyMatrix(graphMatrix, tempMatrix);

            String s1 = new String("S" + tempCnt++);
            // System.out.println("Adding dummy "+s1);
            m_nodes.add(new GraphNode(s1, s1, SINGULAR_DUMMY));

            int temp3[] = new int[nodeLevels[level].length + 1];
            System.arraycopy(nodeLevels[level], 0, temp3, 0,
              nodeLevels[level].length);
            temp3[temp3.length - 1] = m_nodes.size() - 1;
            nodeLevels[level] = temp3;
            temp3 = new int[m_nodes.size() + 1];
            System.arraycopy(nodesLevel, 0, temp3, 0, nodesLevel.length);
            temp3[m_nodes.size() - 1] = level;
            nodesLevel = temp3;
            level++;
            // nodeLevels[level++].addElement(new Integer(m_nodes.size()-1));
            // System.out.println("len:"+len+"("+
            // ((GraphNode)m_nodes.get(len)).ID+"),"+
            // nodesLevel[i]+","+nodesLevel[tempnode]);

            int m;
            for (m = len; m < len + nodesLevel[i] - nodesLevel[tempnode] - 1
              - 1; m++) {
              String s2 = new String("S" + tempCnt++);
              // System.out.println("Adding dummy "+s2);
              m_nodes.add(new GraphNode(s2, s2, SINGULAR_DUMMY));
              temp3 = new int[nodeLevels[level].length + 1];
              // for(int j=0; j<nodeLevels[level].length; j++)
              // temp3[j] = nodeLevels[level][j];
              System.arraycopy(nodeLevels[level], 0, temp3, 0,
                nodeLevels[level].length);
              temp3[temp3.length - 1] = m_nodes.size() - 1;
              nodeLevels[level] = temp3;
              temp3 = new int[m_nodes.size() + 1];
              System.arraycopy(nodesLevel, 0, temp3, 0, nodesLevel.length);
              temp3[m_nodes.size() - 1] = level;
              nodesLevel = temp3;
              level++;
              // nodeLevels[level++].addElement(new Integer(m_nodes.size()-1));
              // System.out.println("modifying "+
              // ((GraphNode)nodes.get(m)).ID+", "+
              // ((GraphNode)nodes.get(m+1)).ID);
              tempMatrix[m][m + 1] = tempMatrix[n][i]; // tempCnt++;
              if (m > len) {
                // System.out.println("modifying "+
                // ((GraphNode)nodes.get(m)).ID+
                // ", "+((GraphNode)nodes.get(m-1)).ID);
                tempMatrix[m][m - 1] = -1 * tempMatrix[n][i];
              }
            }
            // System.out.println("m "+((GraphNode)m_nodes.get(m)).ID+
            // " i "+((GraphNode)m_nodes.get(i)).ID+
            // " tempnode "+((GraphNode)m_nodes.get(tempnode)).ID+
            // " len "+((GraphNode)m_nodes.get(len)).ID );
            // System.out.println("modifying "+
            // ((GraphNode)nodes.get(m)).ID+", "+
            // ((GraphNode)nodes.get(i)).ID);

            // temp[lastTempNodeCreated][targetNode]=temp[origNode][targetNode]
            tempMatrix[m][i] = tempMatrix[n][i];
            // System.out.println("modifying "+
            // ((GraphNode)nodes.get(tempnode)).ID+", "+
            // ((GraphNode)nodes.get(len)).ID);

            // temp[origNode][firstTempNodecreated] = temp[origNode][targetNode]
            tempMatrix[tempnode][len] = tempMatrix[n][i];
            // System.out.println("modifying "+
            // ((GraphNode)nodes.get(len)).ID+", "+
            // ((GraphNode)nodes.get(tempnode)).ID);

            // temp[firstTempNodeCreated][origNode] for reverse tracing
            tempMatrix[len][tempnode] = -1 * tempMatrix[n][i];
            // System.out.println("modifying "+
            // ((GraphNode)nodes.get(i)).ID+", "+
            // ((GraphNode)nodes.get(m)).ID);

            // temp[targetNode][lastTempNodecreated] for reverse tracing
            tempMatrix[i][m] = -1 * tempMatrix[n][i];
            if (m > len) {
              // System.out.println("modifying "+
              // ((GraphNode)nodes.get(m)).ID+
              // ", "+((GraphNode)nodes.get(m-1)).ID);

              // temp[lastTempNodeCreated][secondlastNode] for reverse tracing
              // but only do this if more than 1 temp nodes are created
              tempMatrix[m][m - 1] = -1 * tempMatrix[n][i];
            }

            // temp[origNode][targetNode] = 0 unlinking as they have been
            tempMatrix[n][i] = 0;

            // linked by a chain of temporary nodes now.
            tempMatrix[i][n] = 0;

            graphMatrix = tempMatrix;
          } else {
            // System.out.println("modifying "+
            // ((GraphNode)nodes.get(i)).ID+", "+
            // ((GraphNode)nodes.get(n)).ID);
            // ****Even if there is no gap just add a reference for the
            // ****parent to the child for reverse tracing, useful if the
            // ****there is a reversed edge from parent to child and therefore
            // ****visualizer would know to highlight this edge when
            // ****highlighting the child.
            graphMatrix[i][n] = -1 * graphMatrix[n][i];
          }
        }
      }
    }

  }

  /**
   * Returns the index of an element in a level. Must never be called with the
   * wrong element and the wrong level, will throw an exception otherwise. It
   * takes as agrument the index of the element (in the m_nodes vector) and the
   * level it is supposed to be in (as each level contains the indices of the
   * nodes present in that level).
   */
  private int indexOfElementInLevel(int element, int level[]) throws Exception {
    for (int i = 0; i < level.length; i++) {
      if (level[i] == element) {
        return i;
      }
    }
    throw new Exception("Error. Didn't find element " + m_nodes.get(element).ID
      + " in level. Inspect code for "
      + "weka.gui.graphvisualizer.HierarchicalBCEngine");
  }

  /**
   * Computes the number of edge crossings in the whole graph Takes as an
   * argument levels of nodes. It is essentially the same algorithm provided in
   * Universitat des Saarlandes technical report A03/94 by Georg Sander.
   */
  protected int crossings(final int levels[][]) {
    int sum = 0;

    for (int i = 0; i < levels.length - 1; i++) {
      // System.out.println("*****************Processing level "+i+
      // "*****************************");
      MyList upper = new MyList(), lower = new MyList();
      MyListNode lastOcrnce[] = new MyListNode[m_nodes.size()];
      int edgeOcrnce[] = new int[m_nodes.size()];

      for (int j = 0, uidx = 0, lidx = 0; j < (levels[i].length + levels[i + 1].length); j++) {
        if ((j % 2 == 0 && uidx < levels[i].length)
          || lidx >= levels[i + 1].length) {
          int k1 = 0, k2 = 0, k3 = 0;
          GraphNode n = m_nodes.get(levels[i][uidx]);
          // Deactivating and counting crossings for all edges ending in it
          // coming from bottom left
          if (lastOcrnce[levels[i][uidx]] != null) {
            MyListNode temp = new MyListNode(-1);
            temp.next = upper.first;
            try {
              do {
                temp = temp.next;
                if (levels[i][uidx] == temp.n) {
                  k1 = k1 + 1;
                  k3 = k3 + k2;
                  // System.out.println("Removing from upper: "+temp.n);
                  upper.remove(temp);
                } else {
                  k2 = k2 + 1;
                }
              } while (temp != lastOcrnce[levels[i][uidx]]);
            } catch (NullPointerException ex) {
              System.out.println("levels[i][uidx]: " + levels[i][uidx]
                + " which is: " + m_nodes.get(levels[i][uidx]).ID + " temp: "
                + temp + " upper.first: " + upper.first);
              ex.printStackTrace();
              System.exit(-1);
            }

            lastOcrnce[levels[i][uidx]] = null;
            sum = sum + k1 * lower.size() + k3;
          }
          // Activating all the edges going out towards the bottom
          // and bottom right
          for (int k = 0; k < n.edges.length; k++) {
            if (n.edges[k][1] > 0) {
              try {
                if (indexOfElementInLevel(n.edges[k][0], levels[i + 1]) >= uidx) {
                  edgeOcrnce[n.edges[k][0]] = 1;
                }
              } catch (Exception ex) {
                ex.printStackTrace();
              }
            }
          }
          for (int k = 0; k < levels[i + 1].length; k++) {
            if (edgeOcrnce[levels[i + 1][k]] == 1) {
              MyListNode temp = new MyListNode(levels[i + 1][k]); // new
                                                                  // MyListNode(n.edges[k][0]);
              lower.add(temp);
              lastOcrnce[levels[i + 1][k]] = temp;
              edgeOcrnce[levels[i + 1][k]] = 0;
              // System.out.println("Adding to lower: "+levels[i+1][k]+
              // " which is: "+((GraphNode)m_nodes.get(levels[i+1][k])).ID+
              // " first's n is: "+lower.first.n);
            }

          }
          uidx++;
        } else {
          int k1 = 0, k2 = 0, k3 = 0;
          GraphNode n = m_nodes.get(levels[i + 1][lidx]);
          // Deactivating and counting crossings for all edges ending in it
          // coming from up and upper left
          if (lastOcrnce[levels[i + 1][lidx]] != null) {

            MyListNode temp = new MyListNode(-1);
            temp.next = lower.first;
            try {
              do {
                temp = temp.next;
                if (levels[i + 1][lidx] == temp.n) {
                  k1 = k1 + 1;
                  k3 = k3 + k2;
                  lower.remove(temp);
                  // System.out.println("Removing from lower: "+temp.n);
                } else {
                  k2 = k2 + 1;
                  // System.out.println("temp: "+temp+" lastOcrnce: "+
                  // lastOcrnce[levels[i+1][lidx]]+" temp.n: "+
                  // temp.n+" lastOcrnce.n: "+
                  // lastOcrnce[levels[i+1][lidx]].n);
                }
              } while (temp != lastOcrnce[levels[i + 1][lidx]]);
            } catch (NullPointerException ex) {
              System.out.print("levels[i+1][lidx]: " + levels[i + 1][lidx]
                + " which is: " + m_nodes.get(levels[i + 1][lidx]).ID
                + " temp: " + temp);
              System.out.println(" lower.first: " + lower.first);
              ex.printStackTrace();
              System.exit(-1);
            }

            lastOcrnce[levels[i + 1][lidx]] = null;
            sum = sum + k1 * upper.size() + k3;
          }

          // Activating all the edges going out towards the upper right
          for (int k = 0; k < n.edges.length; k++) {
            if (n.edges[k][1] < 0) {
              try {
                if (indexOfElementInLevel(n.edges[k][0], levels[i]) > lidx) {
                  edgeOcrnce[n.edges[k][0]] = 1;
                }
              } catch (Exception ex) {
                ex.printStackTrace();
              }
            }
          }
          for (int k = 0; k < levels[i].length; k++) {
            if (edgeOcrnce[levels[i][k]] == 1) {
              MyListNode temp = new MyListNode(levels[i][k]);
              upper.add(temp);
              lastOcrnce[levels[i][k]] = temp;
              edgeOcrnce[levels[i][k]] = 0;
              // System.out.println("Adding to upper: "+levels[i][k]+
              // " which is : "+
              // ((GraphNode)m_nodes.get(levels[i][k])).ID+
              // " from node: "+n.ID+", "+k+
              // " first's value: "+upper.first.n);
            }
          }
          lidx++;
        }
      }
      // System.out.println("Sum at the end is: "+sum);
    }

    return sum;
  }

  /**
   * The following two methods remove cycles from the graph.
   */
  protected void removeCycles() {
    // visited[x]=1 is only visited AND visited[x]=2 means node is visited
    // and is on the current path
    int visited[] = new int[m_nodes.size()];

    for (int i = 0; i < graphMatrix.length; i++) {
      if (visited[i] == 0) {
        removeCycles2(i, visited);
        visited[i] = 1;
      }
    }
  }

  /**
   * This method should not be called directly. It should be called only from to
   * call removeCycles()
   */
  private void removeCycles2(int nindex, int visited[]) {
    visited[nindex] = 2;
    for (int i = 0; i < graphMatrix[nindex].length; i++) {
      if (graphMatrix[nindex][i] == DIRECTED) {
        if (visited[i] == 0) {
          removeCycles2(i, visited);
          visited[i] = 1;
        } else if (visited[i] == 2) {
          if (nindex == i) {
            graphMatrix[nindex][i] = 0;
          } else if (graphMatrix[i][nindex] == DIRECTED) {
            // System.out.println("\nFound double "+nindex+','+i);
            graphMatrix[i][nindex] = DOUBLE;
            graphMatrix[nindex][i] = -DOUBLE;
          } else {
            // System.out.println("\nReversing "+nindex+','+i);
            graphMatrix[i][nindex] = REVERSED;
            graphMatrix[nindex][i] = -REVERSED;
          }
        }
      }
    }
  }

  /**
   * This method assigns a vertical level to each node. See
   * makeProperHierarchy() to see how to use it.
   */
  protected void assignLevels(int levels[], int depth, int i, int j) {
    // System.out.println(i+","+j);
    if (i >= graphMatrix.length) {
      return;
    } else if (j >= graphMatrix[i].length) {
      return;
    }
    if (graphMatrix[i][j] <= 0) {
      assignLevels(levels, depth, i, ++j);
    } else if (graphMatrix[i][j] == DIRECTED || graphMatrix[i][j] == DOUBLE) {
      if (depth + 1 > levels[j]) {
        levels[j] = depth + 1;
        assignLevels(levels, depth + 1, j, 0);
      }
      assignLevels(levels, depth, i, ++j);
    }
  }

  /**
   * This method minimizes the number of edge crossings using the BaryCenter
   * heuristics given by Sugiyama et al. 1981 This method processes the graph
   * topdown if reversed is false, otherwise it does bottomup.
   */
  private int[][] minimizeCrossings(boolean reversed, int nodeLevels[][]) {

    // Minimizing crossings using Sugiyama's method
    if (reversed == false) {
      for (int times = 0; times < 1; times++) {
        int tempLevels[][] = new int[nodeLevels.length][];

        // System.out.println("---------------------------------");
        // System.out.println("Crossings before PHaseID: "+
        // crossings(nodeLevels));
        copy2DArray(nodeLevels, tempLevels);
        for (int i = 0; i < nodeLevels.length - 1; i++) {
          phaseID(i, tempLevels);
        }
        if (crossings(tempLevels) < crossings(nodeLevels)) {
          nodeLevels = tempLevels;
        }

        // System.out.println("\nCrossings before PHaseIU: "+
        // crossings(nodeLevels));
        tempLevels = new int[nodeLevels.length][];
        copy2DArray(nodeLevels, tempLevels);
        for (int i = nodeLevels.length - 2; i >= 0; i--) {
          phaseIU(i, tempLevels);
        }
        if (crossings(tempLevels) < crossings(nodeLevels)) {
          nodeLevels = tempLevels;
        }

        // System.out.println("\nCrossings before PHaseIID: "+
        // crossings(nodeLevels));
        tempLevels = new int[nodeLevels.length][];
        copy2DArray(nodeLevels, tempLevels);
        for (int i = 0; i < nodeLevels.length - 1; i++) { // Down
          phaseIID(i, tempLevels);
        }
        if (crossings(tempLevels) < crossings(nodeLevels)) {
          nodeLevels = tempLevels;
          // System.out.println("Crossings temp:"+crossings(tempLevels)+
          // " graph:"+crossings(nodeLevels));
          // printMatrices(nodeLevels);
        }

        // System.out.println("\nCrossings before PHaseIIU: "+
        // crossings(nodeLevels));
        tempLevels = new int[nodeLevels.length][];
        copy2DArray(nodeLevels, tempLevels);
        for (int i = nodeLevels.length - 2; i >= 0; i--) { // Up
          phaseIIU(i, tempLevels);
        }
        if (crossings(tempLevels) < crossings(nodeLevels)) {
          nodeLevels = tempLevels;
          // /System.out.println("Crossings temp:"+crossings(tempLevels)+
          // " graph:"+crossings(nodeLevels));
          // /printMatrices(nodeLevels);
          // System.out.println("\nCrossings after phaseIIU: "+
          // crossings(nodeLevels));
        }
      }
      return nodeLevels;
    } else {
      for (int times = 0; times < 1; times++) {
        int tempLevels[][] = new int[nodeLevels.length][];

        // System.out.println("---------------------------------");
        // System.out.println("\nCrossings before PHaseIU: "+
        // crossings(nodeLevels));
        copy2DArray(nodeLevels, tempLevels);
        for (int i = nodeLevels.length - 2; i >= 0; i--) {
          phaseIU(i, tempLevels);
        }
        if (crossings(tempLevels) < crossings(nodeLevels)) {
          nodeLevels = tempLevels;
          // printMatrices(nodeLevels);
        }

        // System.out.println("Crossings before PHaseID: "+
        // crossings(nodeLevels));
        tempLevels = new int[nodeLevels.length][];
        copy2DArray(nodeLevels, tempLevels);
        for (int i = 0; i < nodeLevels.length - 1; i++) {
          phaseID(i, tempLevels);
        }
        if (crossings(tempLevels) < crossings(nodeLevels)) {
          nodeLevels = tempLevels;
          // /printMatrices(nodeLevels);
        }

        // System.out.println("\nCrossings before PHaseIIU: "+
        // crossings(nodeLevels));
        tempLevels = new int[nodeLevels.length][];
        copy2DArray(nodeLevels, tempLevels);
        for (int i = nodeLevels.length - 2; i >= 0; i--) { // Up
          phaseIIU(i, tempLevels);
        }
        if (crossings(tempLevels) < crossings(nodeLevels)) {
          nodeLevels = tempLevels;
          // printMatrices(nodeLevels);
        }

        // System.out.println("\nCrossings before PHaseIID: "+
        // crossings(nodeLevels));
        tempLevels = new int[nodeLevels.length][];
        copy2DArray(nodeLevels, tempLevels);
        for (int i = 0; i < nodeLevels.length - 1; i++) { // Down
          phaseIID(i, tempLevels);
        }
        if (crossings(tempLevels) < crossings(nodeLevels)) {
          nodeLevels = tempLevels;
          // /printMatrices(nodeLevels);
          // System.out.println("\nCrossings after phaseIID: "+
          // crossings(nodeLevels));
        }
      }
      return nodeLevels;
    }
  }

  /**
   * See Sugiyama et al. 1981 (full reference give at top) lindex is the index
   * of the level we want to process. In this method we'll sort the vertices at
   * the level one below lindex according to their UP-barycenters (or column
   * barycenters).
   */
  protected void phaseID(final int lindex, final int levels[][]) {
    float colBC[]; // = new float[levels[lindex+1].size()];
    colBC = calcColBC(lindex, levels);

    // System.out.println("In ID Level"+(lindex+1)+":");
    // System.out.print("\t");
    // for(int i=0; i<colBC.length; i++)
    // {System.out.print("Col"+(i+1)+":"+colBC[i]+" ");
    // }
    // System.out.println("");
    // colBC = calcColBC1(lindex, levels);
    // for(int i=0; i<colBC.length; i++)
    // {System.out.print("Col"+(i+1)+":"+colBC[i]+" ");
    // }
    // System.out.println("");
    // System.out.print("\n\tNodes ");
    // for(int i=0; i<levels[lindex+1].length; i++)
    // System.out.print(levels[lindex+1][i]+" ");
    // System.out.println("");
    // System.out.println("\nCrossings: "+crossings(levels));
    // inspect(false, lindex, levels, colBC);

    isort(levels[lindex + 1], colBC);
    // combSort11(levels[lindex+1], colBC);
    // System.out.println("After sorting");
    // System.out.print("\t");
    // for(int i=0; i<colBC.length; i++)
    // {System.out.print("Col"+(i+1)+":"+colBC[i]+" ");
    // }
    // System.out.print("\n\tNodes ");
    // for(int i=0; i<levels[lindex+1].length; i++)
    // System.out.print(levels[lindex+1][i]+" ");
    // System.out.println("\nCrossings: "+crossings(levels));
    // /System.out.println("");
  }

  /**
   * See Sugiyama et al. 1981 (full reference give at top) lindex is the index
   * of the level we want to process. In this method we'll sort the vertices at
   * the level lindex according to their DOWN-barycenters (or row barycenters).
   */
  public void phaseIU(final int lindex, final int levels[][]) {
    float rowBC[];
    rowBC = calcRowBC(lindex, levels);

    // System.out.println("In IU Level"+(lindex+1)+":");
    // System.out.print("\t");
    // for(int i=0; i<rowBC.length; i++)
    // {System.out.print("Row"+(i+1)+":"+rowBC[i]+" ");
    // }
    // System.out.print("\n\t");
    // rowBC = calcRowBC1(lindex, levels);
    // for(int i=0; i<rowBC.length; i++)
    // {System.out.print("Row"+(i+1)+":"+rowBC[i]+" ");
    // }
    // System.out.println("");
    // System.out.print("\n\tNodes ");
    // for(int i=0; i<levels[lindex].length; i++)
    // System.out.print(levels[lindex][i]+" ");
    // System.out.println("\nCrossings: "+crossings(levels));
    // inspect(true, lindex, levels, rowBC);

    isort(levels[lindex], rowBC);
    // combSort11(levels[lindex], rowBC);
    // System.out.println("After sorting\n\t");
    // for(int i=0; i<rowBC.length; i++)
    // {System.out.print("Row"+(i+1)+":"+rowBC[i]+" ");
    // }
    // System.out.print("\n\tNodes ");
    // for(int i=0; i<levels[lindex].length; i++)
    // System.out.print(levels[lindex][i]+" ");
    // System.out.println("\nCrossings: "+crossings(levels));
  }

  /**
   * See Sugiyama et al. 1981 (full reference give at top)
   */
  public void phaseIID(final int lindex, final int levels[][]) {
    float colBC[];
    colBC = calcColBC(lindex, levels);

    // System.out.println("getting into phase IID");
    for (int i = 0; i < colBC.length - 1; i++) {
      if (colBC[i] == colBC[i + 1]) {
        // System.out.println("Crossings before begining of iteration: "+
        // crossings(levels));
        int tempLevels[][] = new int[levels.length][];
        copy2DArray(levels, tempLevels);
        // System.out.println("Interchanging: "+
        // ((GraphNode)m_nodes.get(levels[lindex+1][i])).ID+
        // " & "+
        // ((GraphNode)m_nodes.get(levels[lindex+1][(i+1)])).ID+
        // " at level "+(lindex+1) );
        int node1 = levels[lindex + 1][i];
        int node2 = levels[lindex + 1][i + 1];
        levels[lindex + 1][i + 1] = node1;
        levels[lindex + 1][i] = node2;

        for (int k = lindex + 1; k < levels.length - 1; k++) {
          phaseID(k, levels);
        }
        // System.out.println("Crossings temp:"+crossings(tempLevels)+
        // " graph:"+crossings(levels));
        if (crossings(levels) <= crossings(tempLevels)) {
          // System.out.println("Crossings temp: "+crossings(tempLevels)+
          // " Crossings levels: "+crossings(levels));
          copy2DArray(levels, tempLevels);
        } // printMatrices(levels); }
        else {
          copy2DArray(tempLevels, levels);
          levels[lindex + 1][i + 1] = node1;
          levels[lindex + 1][i] = node2;
        }
        // System.out.println("Crossings after PhaseID of phaseIID, "+
        // "in iteration "+i+" of "+(colBC.length-1)+" at "+
        // lindex+", levels: "+crossings(levels)+
        // " temp: "+crossings(tempLevels));

        // tempLevels = new int[levels.length][];
        // copy2DArray(levels, tempLevels);
        for (int k = levels.length - 2; k >= 0; k--) {
          phaseIU(k, levels);
        }
        // System.out.println("Crossings temp:"+crossings(tempLevels)+
        // " graph:"+crossings(levels));
        // if(crossings(tempLevels)<crossings(levels)) {
        // System.out.println("Crossings temp: "+crossings(tempLevels)+
        // " Crossings levels: "+crossings(levels));
        // copy2DArray(tempLevels, levels); } //printMatrices(levels); }
        if (crossings(tempLevels) < crossings(levels)) {
          copy2DArray(tempLevels, levels);
        }

        // System.out.println("Crossings after PhaseIU of phaseIID, in"+
        // " iteration "+i+" of "+(colBC.length-1)+" at "
        // +lindex+", levels: "+crossings(levels)+" temp: "+
        // crossings(tempLevels));
        // colBC = calcColBC(lindex, levels);
      }
    }
  }

  /**
   * See Sugiyama et al. 1981 (full reference give at top)
   */
  public void phaseIIU(final int lindex, final int levels[][]) {
    float rowBC[];
    rowBC = calcRowBC(lindex, levels);

    // System.out.println("Getting into phaseIIU");
    for (int i = 0; i < rowBC.length - 1; i++) {
      if (rowBC[i] == rowBC[i + 1]) {
        // System.out.println("Crossings before begining of iteration: "+
        // crossings(levels));
        int tempLevels[][] = new int[levels.length][];
        copy2DArray(levels, tempLevels);
        // System.out.println("Interchanging: "+
        // ((GraphNode)m_nodes.get(levels[lindex][i])).ID+" & "+
        // ((GraphNode)m_nodes.get(levels[lindex][i+1])).ID+
        // " at level "+(lindex+1) );
        int node1 = levels[lindex][i];
        int node2 = levels[lindex][i + 1];
        levels[lindex][i + 1] = node1;
        levels[lindex][i] = node2;

        for (int k = lindex - 1; k >= 0; k--) {
          phaseIU(k, levels);
        }
        if (crossings(levels) <= crossings(tempLevels)) {
          // System.out.println("Crossings temp: "+crossings(tempLevels)+
          // " Crossings levels: "+crossings(levels));
          copy2DArray(levels, tempLevels);
        } // printMatrices(levels);
        else {
          copy2DArray(tempLevels, levels);
          levels[lindex][i + 1] = node1;
          levels[lindex][i] = node2;
        }
        // System.out.println("Crossings after PhaseIU of PhaseIIU, in "+
        // "iteration "+i+" of "+(rowBC.length-1)+" at "
        // +lindex+", levels: "+crossings(levels)+
        // " temp: "+crossings(tempLevels));

        // tempLevels = new int[levels.length][];
        // copy2DArray(levels, tempLevels);
        for (int k = 0; k < levels.length - 1; k++) {
          phaseID(k, levels);
        }
        // if(crossings(tempLevels)<crossings(levels)) {
        // System.out.println("Crossings temp: "+crossings(tempLevels)+
        // " Crossings levels: "+crossings(levels));
        // copy2DArray(tempLevels, levels); } //printMatrices(levels); }
        if (crossings(tempLevels) <= crossings(levels)) {
          copy2DArray(tempLevels, levels);
          // System.out.println("Crossings after PhaseID of phaseIIU, in "+
          // "iteration "+i+" of "+(rowBC.length-1)+" at "
          // +lindex+", levels: "+crossings(levels)+
          // " temp: "+crossings(tempLevels));
          // rowBC = calcRowBC(lindex, levels);
        }
      }
    }
  }

  /**
   * See Sugiyama et al. 1981 (full reference give at top)
   */
  protected float[] calcRowBC(final int lindex, final int levels[][]) {
    float rowBC[] = new float[levels[lindex].length];
    GraphNode n;

    for (int i = 0; i < levels[lindex].length; i++) {
      int sum = 0;
      n = m_nodes.get(levels[lindex][i]);

      for (int[] edge : n.edges) {
        if (edge[1] > 0) {
          sum++;
          try {
            rowBC[i] = rowBC[i]
              + indexOfElementInLevel(edge[0], levels[lindex + 1]) + 1;
          } catch (Exception ex) {
            return null;
          }
        }
      }
      if (rowBC[i] != 0) {
        rowBC[i] = rowBC[i] / sum;
      }
    }
    return rowBC;
  }

  /**
   * See Sugiyama et al. 1981 (full reference give at top)
   */
  protected float[] calcColBC(final int lindex, final int levels[][]) {
    float colBC[] = new float[levels[lindex + 1].length];
    GraphNode n;

    for (int i = 0; i < levels[lindex + 1].length; i++) {
      int sum = 0;
      n = m_nodes.get(levels[lindex + 1][i]);

      for (int[] edge : n.edges) {
        if (edge[1] < 1) {
          sum++;
          try {
            colBC[i] = colBC[i]
              + indexOfElementInLevel(edge[0], levels[lindex]) + 1;
          } catch (Exception ex) {
            return null;
          }
        }
      }
      if (colBC[i] != 0) {
        colBC[i] = colBC[i] / sum;
      }
    }
    return colBC;
  }

  /**
   * Prints out the interconnection matrix at each level. See Sugiyama et al.
   * 1981 (full reference give at top)
   */
  protected void printMatrices(final int levels[][]) {
    int i = 0;
    for (i = 0; i < levels.length - 1; i++) {
      float rowBC[] = null;
      float colBC[] = null;
      try {
        rowBC = calcRowBC(i, levels);
        colBC = calcColBC(i, levels);
      } catch (NullPointerException ne) {
        System.out.println("i: " + i + " levels.length: " + levels.length);
        ne.printStackTrace();
        return;
      }

      System.out.print("\nM" + (i + 1) + "\t");
      for (int j = 0; j < levels[i + 1].length; j++) {
        System.out.print(m_nodes.get(levels[i + 1][j]).ID + " ");
        // ((Integer)levels[i+1].get(j)).intValue())+" ");
      }
      System.out.println("");

      for (int j = 0; j < levels[i].length; j++) {
        System.out.print(m_nodes.get(levels[i][j]).ID + "\t");
        // ((Integer)levels[i].get(j)).intValue())+"\t");
        for (int k = 0; k < levels[i + 1].length; k++) {

          System.out.print(graphMatrix[levels[i][j]]
          // ((Integer)levels[i].get(j)).intValue()]
            [levels[i + 1][k]]
            + " ");
          // ((Integer)levels[i+1].get(k)).intValue()]+" ");

        }
        System.out.println(rowBC[j]);
      }
      System.out.print("\t");
      for (int k = 0; k < levels[i + 1].length; k++) {
        System.out.print(colBC[k] + " ");
      }
    }
    System.out.println("\nAt the end i: " + i + " levels.length: "
      + levels.length);
  }

  /**
   * This methods sorts the vertices in level[] according to their barycenters
   * in BC[], using combsort11. It, however, doesn't touch the vertices with
   * barycenter equal to zero.
   */
  /*
   * //This method should be removed protected static void combSort11(int
   * level[], float BC[]) { int switches, j, top, gap, lhold; float hold; gap =
   * BC.length; do { gap=(int)(gap/1.3); switch(gap) { case 0: gap = 1; break;
   * case 9: case 10: gap=11; break; default: break; } switches=0; top =
   * BC.length-gap; for(int i=0; i<top; i++) { j=i+gap; if(BC[i]==0 || BC[j]==0)
   * continue; if(BC[i] > BC[j]) { hold=BC[i]; BC[i]=BC[j]; BC[j]=hold; lhold =
   * level[i]; level[i] = level[j]; level[j] = lhold; switches++; }//endif
   * }//endfor }while(switches>0 || gap>1); }
   */

  /**
   * This methods sorts the vertices in level[] according to their barycenters
   * in BC[], using insertion sort. It, however, doesn't touch the vertices with
   * barycenter equal to zero.
   */
  // Both level and BC have elements in the same order
  protected static void isort(int level[], float BC[]) {
    float temp;
    int temp2;
    for (int i = 0; i < BC.length - 1; i++) {

      int j = i;
      temp = BC[j + 1];
      temp2 = level[j + 1];
      if (temp == 0) {
        continue;
      }
      int prej = j + 1;

      while (j > -1 && (temp < BC[j] || BC[j] == 0)) {
        if (BC[j] == 0) {
          j--;
          continue;
        } else {
          BC[prej] = BC[j];
          level[prej] = level[j];
          prej = j;
          j--;
        }
      }
      // j++;
      BC[prej] = temp;
      level[prej] = temp2;
      // Integer node = (Integer)level.get(i+1);
      // level.remove(i+1);
      // level.insertElementAt(node, prej);
    }
  }

  /**
   * Copies one Matrix of type int[][] to another.
   */
  protected void copyMatrix(int from[][], int to[][]) {
    for (int i = 0; i < from.length; i++) {
      for (int j = 0; j < from[i].length; j++) {
        to[i][j] = from[i][j];
      }
    }
  }

  /**
   * Copies one array of type int[][] to another.
   */
  protected void copy2DArray(int from[][], int to[][]) {
    for (int i = 0; i < from.length; i++) {
      to[i] = new int[from[i].length];
      System.arraycopy(from[i], 0, to[i], 0, from[i].length);
      // for(int j=0; j<from[i].length; j++)
      // to[i][j] = from[i][j];
    }
  }

  /**
   * This method lays out the vertices horizontally, in each level. It simply
   * assings an x value to a vertex according to its index in the level.
   */
  protected void naiveLayout() {
    /*
     * if(maxStringWidth==0) { int strWidth; for(int i=0; i<m_nodes.size(); i++)
     * { strWidth = m_fm.stringWidth(((GraphNode)m_nodes.get(i)).lbl);
     * if(strWidth>maxStringWidth) maxStringWidth=strWidth; }
     * 
     * if(m_nodeSize<maxStringWidth) {m_nodeSize = maxStringWidth+4; m_nodeArea
     * = m_nodeSize+8; } }
     */
    if (nodeLevels == null) {
      makeProperHierarchy();
    }

    // int nodeHeight = m_nodeHeight*2; //m_fm.getHeight()*2;
    for (int i = 0, temp = 0; i < nodeLevels.length; i++) {
      for (int j = 0; j < nodeLevels[i].length; j++) {
        temp = nodeLevels[i][j];
        // horPositions[temp]=j;
        GraphNode n = m_nodes.get(temp);
        n.x = j * m_nodeWidth; // horPositions[temp]*m_nodeWidth;
        n.y = i * 3 * m_nodeHeight;
      }
    }
    // setAppropriateSize();
  }

  protected int uConnectivity(int lindex, int eindex) {
    int n = 0;
    for (int i = 0; i < nodeLevels[lindex - 1].length; i++) {
      if (graphMatrix[nodeLevels[lindex - 1][i]][nodeLevels[lindex][eindex]] > 0) {
        n++;
      }
    }

    return n;
  }

  protected int lConnectivity(int lindex, int eindex) {
    int n = 0;
    for (int i = 0; i < nodeLevels[lindex + 1].length; i++) {
      if (graphMatrix[nodeLevels[lindex][eindex]][nodeLevels[lindex + 1][i]] > 0) {
        n++;
      }
    }

    return n;
  }

  protected int uBCenter(int lindex, int eindex, int horPositions[]) {
    int sum = 0;

    for (int i = 0; i < nodeLevels[lindex - 1].length; i++) {
      if (graphMatrix[nodeLevels[lindex - 1][i]][nodeLevels[lindex][eindex]] > 0) {
        sum = sum + (horPositions[nodeLevels[lindex - 1][i]]);
      }
    }
    if (sum != 0) { // To avoid 0/0
      // System.out.println("uBC Result: "+sum+"/"+
      // uConnectivity(lindex,eindex)+
      // " = "+(sum/uConnectivity(lindex,eindex)) );
      sum = sum / uConnectivity(lindex, eindex);
    }
    return sum;
  }

  protected int lBCenter(int lindex, int eindex, int horPositions[]) {
    int sum = 0;

    for (int i = 0; i < nodeLevels[lindex + 1].length; i++) {
      if (graphMatrix[nodeLevels[lindex][eindex]][nodeLevels[lindex + 1][i]] > 0) {
        sum = sum + (horPositions[nodeLevels[lindex + 1][i]]);
      }
    }
    if (sum != 0) {
      sum = sum / lConnectivity(lindex, eindex); // lConectivity;
    }
    return sum;
  }

  /**
   * This method lays out the vertices horizontally, in each level. See Sugiyama
   * et al. 1981 for full reference.
   */
  protected void priorityLayout1() {

    int[] horPositions = new int[m_nodes.size()];
    int maxCount = 0;

    for (int i = 0; i < nodeLevels.length; i++) {
      int count = 0;
      for (int j = 0; j < nodeLevels[i].length; j++) {
        horPositions[nodeLevels[i][j]] = j;
        count++;
      }
      if (count > maxCount) {
        maxCount = count;
      }
    }
    // fireLayoutCompleteEvent( new LayoutCompleteEvent(this) );
    int priorities[], BC[];
    // System.out.println("********Going from 2 to n********");
    for (int i = 1; i < nodeLevels.length; i++) {
      priorities = new int[nodeLevels[i].length];
      BC = new int[nodeLevels[i].length];
      for (int j = 0; j < nodeLevels[i].length; j++) {
        if (m_nodes.get(nodeLevels[i][j]).ID.startsWith("S")) {
          priorities[j] = maxCount + 1;
        } else {
          priorities[j] = uConnectivity(i, j);
        }
        BC[j] = uBCenter(i, j, horPositions);
      }
      // for(int j=0; j<nodeLevels[i].length; j++)
      // System.out.println("Level: "+(i+1)+" Node: "
      // +((GraphNode)m_nodes.get(nodeLevels[i][j])).ID
      // +" uConnectivity: "+priorities[j]+" uBC: "+BC[j]+" position: "
      // +horPositions[nodeLevels[i][j]]);
      priorityLayout2(nodeLevels[i], priorities, BC, horPositions);
      // repaint
      // try {
      // tempMethod(horPositions);
      // fireLayoutCompleteEvent( new LayoutCompleteEvent(this) );
      // Thread.sleep(1000);
      // } catch(InterruptedException ie) { ie.printStackTrace(); }

      // for(int j=0; j<nodeLevels[i].length; j++)
      // System.out.println("Level: "+(i+1)+" Node: "
      // +((GraphNode)m_nodes.get(nodeLevels[i][j])).ID
      // +" uConnectivity: "+priorities[j]+" uBC: "+BC[j]+" position: "
      // +horPositions[nodeLevels[i][j]]);
    }

    // System.out.println("********Going from n-1 to 1********");
    for (int i = nodeLevels.length - 2; i >= 0; i--) {
      priorities = new int[nodeLevels[i].length];
      BC = new int[nodeLevels[i].length];
      for (int j = 0; j < nodeLevels[i].length; j++) {
        if (m_nodes.get(nodeLevels[i][j]).ID.startsWith("S")) {
          priorities[j] = maxCount + 1;
        } else {
          priorities[j] = lConnectivity(i, j);
        }
        BC[j] = lBCenter(i, j, horPositions); // , priorities[j]);
      }
      priorityLayout2(nodeLevels[i], priorities, BC, horPositions);
      // repaint();
      // try {
      // tempMethod(horPositions);
      // fireLayoutCompleteEvent( new LayoutCompleteEvent(this) );
      // Thread.sleep(1000);
      // } catch(InterruptedException ie) { ie.printStackTrace(); }

      // for(int j=0; j<nodeLevels[i].length; j++)
      // System.out.println("Level: "+(i+1)+" Node: "
      // +((GraphNode)m_nodes.get(nodeLevels[i][j])).ID
      // +" lConnectivity: "+priorities[j]+" lBC: "+BC[j]+" position: "
      // +horPositions[nodeLevels[i][j]]);
    }

    // System.out.println("********Going from 2 to n again********");
    for (int i = 2; i < nodeLevels.length; i++) {
      priorities = new int[nodeLevels[i].length];
      BC = new int[nodeLevels[i].length];
      for (int j = 0; j < nodeLevels[i].length; j++) {
        if (m_nodes.get(nodeLevels[i][j]).ID.startsWith("S")) {
          priorities[j] = maxCount + 1;
        } else {
          priorities[j] = uConnectivity(i, j);
        }
        BC[j] = uBCenter(i, j, horPositions);
      }
      // for(int j=0; j<nodeLevels[i].length; j++)
      // System.out.println("Level: "+(i+1)+" Node: "
      // +((GraphNode)m_nodes.get(nodeLevels[i][j])).ID
      // +" uConnectivity: "+priorities[j]+" uBC: "+BC[j]+" position: "
      // +horPositions[nodeLevels[i][j]]);
      priorityLayout2(nodeLevels[i], priorities, BC, horPositions);
      // repaint();
      // try {
      // tempMethod(horPositions);
      // fireLayoutCompleteEvent( new LayoutCompleteEvent(this) );
      // Thread.sleep(1000);
      // } catch(InterruptedException ie) { ie.printStackTrace(); }
      // for(int j=0; j<nodeLevels[i].length; j++)
      // System.out.println("Level: "+(i+1)+" Node: "
      // +((GraphNode)m_nodes.get(nodeLevels[i][j])).ID
      // +" uConnectivity: "+priorities[j]+" uBC: "+BC[j]+" position: "
      // +horPositions[nodeLevels[i][j]]);
    }

    int minPosition = horPositions[0];

    for (int horPosition : horPositions) {
      if (horPosition < minPosition) {
        minPosition = horPosition;
      }
    }
    if (minPosition < 0) {
      minPosition = minPosition * -1;
      for (int i = 0; i < horPositions.length; i++) {
        // System.out.print(horPositions[i]);
        horPositions[i] += minPosition;
        // System.out.println(">"+horPositions[i]);
      }
    }

    // int nodeHeight = m_nodeHeight*2; //m_fm.getHeight()*2;
    for (int i = 0, temp = 0; i < nodeLevels.length; i++) {
      for (int j = 0; j < nodeLevels[i].length; j++) {
        temp = nodeLevels[i][j];
        // horPositions[temp]=j;
        GraphNode n = m_nodes.get(temp);
        n.x = horPositions[temp] * m_nodeWidth;
        n.y = i * 3 * m_nodeHeight;
      }
    }
    // setAppropriateSize();
  }

  /**
   * This method is used by priorityLayout1(). It should not be called directly.
   * This method does the actual moving of the vertices in each level based on
   * their priorities and barycenters.
   */
  private void priorityLayout2(int level[], int priorities[], int bCenters[],
    int horPositions[]) {
    int descOrder[] = new int[priorities.length];

    // Getting the indices of priorities in descending order
    descOrder[0] = 0;
    for (int i = 0; i < priorities.length - 1; i++) {
      int j = i;
      int temp = i + 1;

      while (j > -1 && priorities[descOrder[j]] < priorities[temp]) {
        descOrder[j + 1] = descOrder[j];
        j--;
      }
      j++;
      descOrder[j] = temp;
    }

    // System.out.println("\nPriorities:");
    // for(int i=0; i<priorities.length; i++)
    // System.out.print(priorities[i]+" ");
    // System.out.println("\nDescOrder:");
    // for(int i=0; i<descOrder.length; i++)
    // System.out.print(descOrder[i]+" ");

    for (int k = 0; k < descOrder.length; k++) {
      for (int i = 0; i < descOrder.length; i++) {

        int leftCount = 0, rightCount = 0, leftNodes[], rightNodes[];
        for (int j = 0; j < priorities.length; j++) {
          if (horPositions[level[descOrder[i]]] > horPositions[level[j]]) {
            leftCount++;
          } else if (horPositions[level[descOrder[i]]] < horPositions[level[j]]) {
            rightCount++;
          }
        }
        leftNodes = new int[leftCount];
        rightNodes = new int[rightCount];

        for (int j = 0, l = 0, r = 0; j < priorities.length; j++) {
          if (horPositions[level[descOrder[i]]] > horPositions[level[j]]) {
            leftNodes[l++] = j;
          } else if (horPositions[level[descOrder[i]]] < horPositions[level[j]]) {
            rightNodes[r++] = j;
          }
        }

        // ****Moving left
        while (Math.abs(horPositions[level[descOrder[i]]] - 1
          - bCenters[descOrder[i]]) < Math
          .abs(horPositions[level[descOrder[i]]] - bCenters[descOrder[i]])) {

          // ****Checking if it can be moved to left
          int temp = horPositions[level[descOrder[i]]];
          boolean cantMove = false;

          for (int j = leftNodes.length - 1; j >= 0; j--) {
            if (temp - horPositions[level[leftNodes[j]]] > 1) {
              break;
            } else if (priorities[descOrder[i]] <= priorities[leftNodes[j]]) {
              cantMove = true;
              break;
            } else {
              temp = horPositions[level[leftNodes[j]]];
            }
          }
          // if(horPositions[level[descOrder[i]]]-1==
          // horPositions[level[leftNodes[j]]])
          // cantMove = true;
          if (cantMove) {
            break;
          }

          temp = horPositions[level[descOrder[i]]] - 1;
          // ****moving other vertices to left
          for (int j = leftNodes.length - 1; j >= 0; j--) {
            if (temp == horPositions[level[leftNodes[j]]]) {
              // System.out.println("Moving "+
              // ((Node)m_nodes.get(level[leftNodes[j]])).ID+" from "
              // +horPositions[level[leftNodes[j]]]+" to "
              // +(horPositions[level[leftNodes[j]]]-1) );
              horPositions[level[leftNodes[j]]] = temp = horPositions[level[leftNodes[j]]] - 1;
            }

          }
          // System.out.println("Moving main "+
          // ((GraphNode)m_nodes.get(level[descOrder[i]])).ID+" from "
          // +horPositions[level[descOrder[i]]]+" to "
          // +(horPositions[level[descOrder[i]]]-1));
          horPositions[level[descOrder[i]]] = horPositions[level[descOrder[i]]] - 1;
        }

        // ****Moving right
        while (Math.abs(horPositions[level[descOrder[i]]] + 1
          - bCenters[descOrder[i]]) < Math
          .abs(horPositions[level[descOrder[i]]] - bCenters[descOrder[i]])) {
          // ****checking if the vertex can be moved
          int temp = horPositions[level[descOrder[i]]];
          boolean cantMove = false;

          for (int rightNode : rightNodes) {
            if (horPositions[level[rightNode]] - temp > 1) {
              break;
            } else if (priorities[descOrder[i]] <= priorities[rightNode]) {
              cantMove = true;
              break;
            } else {
              temp = horPositions[level[rightNode]];
            }
          }
          // if(horPositions[level[descOrder[i]]]-1==
          // horPositions[level[leftNodes[j]]])
          // cantMove = true;
          if (cantMove) {
            break;
          }

          temp = horPositions[level[descOrder[i]]] + 1;
          // ****moving other vertices to left
          for (int j = 0; j < rightNodes.length; j++) {
            if (temp == horPositions[level[rightNodes[j]]]) {
              // System.out.println("Moving "+
              // (Node)m_nodes.get(level[rightNodes[j]])).ID+" from "
              // +horPositions[level[rightNodes[j]]]+" to "
              // +(horPositions[level[rightNodes[j]]]+1) );
              horPositions[level[rightNodes[j]]] = temp = horPositions[level[rightNodes[j]]] + 1;
            }
          }
          // System.out.println("Moving main "+
          // ((GraphNode)m_nodes.get(level[descOrder[i]])).ID+" from "
          // +horPositions[level[descOrder[i]]]+" to "
          // +(horPositions[level[descOrder[i]]]+1));
          horPositions[level[descOrder[i]]] = horPositions[level[descOrder[i]]] + 1;
        }
      }
    }
  }

  /**
   * The following classes implement a double linked list to be used in the
   * crossings function.
   */
  private class MyList {
    int size;
    MyListNode first = null;
    MyListNode last = null;

    public void add(MyListNode n) {
      if (first == null) {
        first = last = n;
      } else if (last.next == null) {
        last.next = n;
        last.next.previous = last;
        last = last.next;
      } else {
        System.err.println("Error shouldn't be in here. Check MyList code");
        size--;
      }

      size++;
    }

    public void remove(MyListNode n) {
      if (n.previous != null) {
        n.previous.next = n.next;
      }
      if (n.next != null) {
        n.next.previous = n.previous;
      }
      if (last == n) {
        last = n.previous;
      }
      if (first == n) {
        first = n.next;
      }

      size--;
    }

    public int size() {
      return size;
    }

  }

  private class MyListNode {
    int n;
    MyListNode next, previous;

    public MyListNode(int i) {
      n = i;
      next = null;
      previous = null;
    }
  }

} // HierarchicalBCEngine
